System of Difference Constraints
问题描述
首先先引入一个通用的线性规划问题，给定一个$m \times n$的矩阵A，一个$m$维的向量$b$和一个$n$维向量$c$。希望能够找到一个$n$维的向量$x$，使得在由$Ax \leqslant b$给定的$m$个约束条件下优化目标函数$\sum_{i = 1}^n c_ix_i$，使得目标函数的取值最大。有时，我们并不关心目标函数，而是仅仅希望能找到一个可行解，即找到任何满足$Ax \leqslant b$的向量$x$，或者判断不存在可行解。
观察一个特例情况，如果线性规划的矩阵$A$的每一行包括一个1和一个-1，其他的所有项皆为0。则对于$Ax \leqslant b$所给出的约束条件变为$m$个涉及$n$个变量的差额限制条件，此时每个约束条件退化为简单的线性不等式：$x_j - x_i \leqslant b_k$。这里$1 \leqslant i, j \leqslant n$，$i \neq j$，且$1 \leqslant k \leqslant m$。
算法介绍
问题建模
对于此类问题，可以从图论的角度进行理解。
在一个$Ax \leqslant b$的差分约束系统中，我们将$m \times n$的线性规划矩阵$A$看作是一张由$n$个节点和$m$条边构成的图的邻接矩阵的转置。这里定义下约束图的概念：
约束图是一个带有权重的有向图$G = (V, E)$，这里
$V = {v_0, v_1, …, v_n }$，$E = {(v_i, v_j): x_j - x_i \leqslant b_k } \bigcup {(v_0, v_1), (v_0, v_2, …, (v_0, v_n)}$。
这里的$v_0$可以看作是一个额外的节点，用来保证图中至少有一个节点，并且从其出发可以到达所有的其他的节点。其中，如果$x_j - x_i \leqslant b_k$是一个差分约束条件，则边$(v_i, v_j)$的权重为$w(v_i, v_j) = b_k$。
举例说明：
对于一组差分约束条件：
可以描绘出如下的差分约束系统的约束图：
其中，$(-5, -3, 0, -1, -4)$为满足条件的一个解。
不难发现，使用最短路算法中的松弛操作：$d(v) - d(u) \leqslant w(u, v)$，刚好可以转为一个差分约束的条件：$i - j \leqslant u$。于是，对于差分约束的问题，可以将未知数$x_i$对应一个顶点，将不等式$x_i - x_j \leqslant c$转化为一条从$x_j$到$x_i$权值为$c$的边。
下面考虑两种特殊情况：
- 无解。当图中出现了负权环的时候，此时的最短路可以无限小，表现为$x_i - x_j \leqslant c$中的$c$可以无限的小，所以满足条件的最大值不存在。
- 有无穷多解。当图中出现了不连通的情况，即起点$s$到终点$t$不可达，此时表示没有约束条件，即有无穷多的解。
求解方法
对于一个最短路问题，经常使用$Dijkstra$算法或$Bellman-Ford$算法进行求解。如果转化的图中没有负权值的边，可以使用复杂度更低的$Dijkstra$算法进行计算。如果存在负权值的情况，当然可以通过$Bellman-Ford$算法进行判断，但是此算法的复杂度是$O(mn)$，我们这里使用改进版的$SPFA$算法进行求解。
|
|
解题报告
Poj 3159 Candies
问题描述
During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a large bag of candies and had flymouse distribute them. All the kids loved candies very much and often compared the numbers of candies they got with others. A kid A could had the idea that though it might be the case that another kid B was better than him in some aspect and therefore had a reason for deserving more candies than he did, he should never get a certain number of candies fewer than B did no matter how many candies he actually got, otherwise he would feel dissatisfied and go to the head-teacher to complain about flymouse’s biased distribution.
snoopy shared class with flymouse at that time. flymouse always compared the number of his candies with that of snoopy’s. He wanted to make the difference between the numbers as large as possible while keeping every kid satisfied. Now he had just got another bag of candies from the head-teacher, what was the largest difference he could make out of it?
Input
The input contains a single test cases. The test cases starts with a line with two integers N and M not exceeding 30 000 and 150 000 respectively. N is the number of kids in the class and the kids were numbered 1 through N. snoopy and flymouse were always numbered 1 and N. Then follow M lines each holding three integers A, B and c in order, meaning that kid A believed that kid Bshould never get over c candies more than he did.
Ouput
Output one line with only the largest difference desired. The difference is guaranteed to be finite.
算法设计
可以看出，每一个孩子在心里对于“公平”都有不同的界定，可以用一个不等式来描述他们每个人能够容忍的最大的差异性对待。
比如$1\ 2\ 5$表述了孩子$1$能够容忍孩子$2$比自己多$5$块糖果。那么可以表达为：$x_2 - x_1 \leqslant 5$，对应到图上是一个从点$x_1$到点$x_2$的一个权值为$5$的边。
分析可知，这里的所有权值都为正数，可以直接使用$Dijkstra$进行编写。
程序代码
|
|
性能分析
此处使用了优先队列优化的$Dijkstra$算法，算法的复杂度为$O(E\lg V)$，空间上使用了链式向前星，减少了建图$malloc$的开销，最后Poj上的开销为：空间 2432K，时间672MS。
编程技术技巧
- 在建图的过程中，如果使用临接矩阵的结构，则空间开销为$O(n^2)$。如果使用临接表结构，此时很难估计规模，需要产生$malloc$的开销。这里使用了链式向前星，预先根据输入的规模开辟数组，通过链表的形式，将边储存下来，进行同时保证了访问的快捷性。
- $Dijkstra$算法可以通过判断是否已经在$V$集合中进行剪枝的操作，避免不必要的运算。经对比发现，速度增加了$100\%$。
Poj 1275 Cashier Employment
问题描述
A supermarket in Tehran is open 24 hours a day every day and needs a number of cashiers to fit its need. The supermarket manager has hired you to help him, solve his problem. The problem is that the supermarket needs different number of cashiers at different times of each day (for example, a few cashiers after midnight, and many in the afternoon) to provide good service to its customers, and he wants to hire the least number of cashiers for this job.
The manager has provided you with the least number of cashiers needed for every one-hour slot of the day. This data is given as R(0), R(1), …, R(23): R(0) represents the least number of cashiers needed from midnight to 1:00 A.M., R(1) shows this number for duration of 1:00 A.M. to 2:00 A.M., and so on. Note that these numbers are the same every day. There are N qualified applicants for this job. Each applicant i works non-stop once each 24 hours in a shift of exactly 8 hours starting from a specified hour, say ti (0 <= ti <= 23), exactly from the start of the hour mentioned. That is, if the ith applicant is hired, he/she will work starting from ti o’clock sharp for 8 hours. Cashiers do not replace one another and work exactly as scheduled, and there are enough cash registers and counters for those who are hired.
You are to write a program to read the R(i) ‘s for i=0..23 and ti ‘s for i=1..N that are all, non-negative integer numbers and compute the least number of cashiers needed to be employed to meet the mentioned constraints. Note that there can be more cashiers than the least number needed for a specific slot.
Input
The first line of input is the number of test cases for this problem (at most 20). Each test case starts with 24 integer numbers representing the R(0), R(1), …, R(23) in one line (R(i) can be at most 1000). Then there is N, number of applicants in another line (0 <= N <= 1000), after which come N lines each containing one ti (0 <= ti <= 23). There are no blank lines between test cases.
Output
For each test case, the output should be written in one line, which is the least number of cashiers needed.
If there is no solution for the test case, you should write No Solution for that case.
算法设计
此题转化为图的分析过程比较复杂，首先已知量是$R_0, R1,\dots, R{23}$表示从$0$开始到$23$点结束每个小时需要的员工数量，同时$B_0, B1, \dots, B{23}$是从这一刻能够开始工作的人的数量，这个数据可以从应聘者这里获得。现在需要解决的问题是，如何求出每个时刻需要开始工作的人数。
如果我们使用$A_0, A1, \dots, A{23}$表示在对应的时刻能够开始工作的人数，因为每个人一天可以工作$8$个小时，所以要考虑到工人跨天的情况，对于$i \geqslant 7$的情况：
$$
A{i-7} + A{i -6} + A_{i - 5} + \dots + A_i \geqslant R_i
$$
对于$0 \leqslant i < 7$的情况：
$$
(A_0 + \dots + Ai)+ (A{i + 17} + \dots + A_{23}) \geqslant R_i
$$
但是，仅仅这个约束条件是不够的，对于$i \in [0, 24)$，我们还有：
$$
0 \leqslant A_i \leqslant B_i
$$
为了方便起见，可以使用$Si = \sum{j = 0}^{i}A_j$来表示一段的和。
则上面的式子可以转化为：
就可以直接将这个式子转化为图进行计算，但是这里注意到，$S{23}$是一个未知量，所以这里需要进行枚举$S{23}$的可能取值，选择一个能够满足条件最小的进行输出。
注意这里有点技巧，$S_{23}$虽然值不大，但是也是$O(n)$级别，和求职者的个数相关，所以可以采用二分查找的方法，将复杂度降低到$O(\lg n)$。
程序代码
|
|
性能分析
由于$SPFA$的算法复杂度由论文可知为$O(kE)$，建图需要$O(n)$，而对于二分查找需要$O(\lg n)$次，所以最后的复杂度是$O(n\lg n)$。最后Poj上开销为空间188K，时间16MS。
编程技术技巧
分配收银员这题，第一次使用了$SPFA$算法，在何时对于不可能的情况（即出现了负权的环）进行剪枝是十分重要的，我们可以在将点入队列前，进行检查，这样可以节省一定的开销。
同时正如前面讲过的，如果出现了一个有序的排列，并且我们需要对其进行搜索，那么此时使用二分法进行查找是十分高效的，必须要将二分法熟练的掌握。
Poj 1201 Intervals
问题描述
You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn.
Write a program that:
reads the number of intervals, their end points and integers c1, …, cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,…,n,
writes the answer to the standard output.
Input
The first line of the input contains an integer n (1 <= n <= 50000) – the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,…,n.
算法设计
题目中给定的条件为每个区间内至少需要选中的点的个数，现在求整个区间需要被选中的点的个数$S$，并且使得$S$最小。
此题的思路可以参考上面的一题，因为最后需要求出一个完整区间的个数，所以直接设$S_i$为$[0, i)$中点的个数。于是，举个例子，如果题目输入$1\ 3\ 1$，则可以转化为：$S_3 - S_1 \geqslant 1$。
当然，值得一提的是，仅仅这些条件是不够的，我们必须要保证每个点最多只能被选中一次。所以有：$1 \geqslant Si - S{i - 1} \geqslant 0$。
程序代码
|
|
性能分析
对于每一次的运算，基本可以看作是$SPFA$的时间开销，即$O(kE)$。在Poj上的运行时间是313MS。
编程技术技巧
这里的区间范围是$[1, 5000]$，可以接受，但是如果输入的数字本身的范围比较小的话，我们可以只考虑题目中出现的范围，这样将图缩小很多，提高运行的速度。
具体来说，输入的时候需要记录本样例的最左边和最右边的值，计算时只需要计算这两个值即可。
###Poj 3169 Layout
问题描述
Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).
Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.
Input
Line 1: Three space-separated integers: N, ML, and MD.
Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.
Output
Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.
算法设计
做完前面的$3$题以后，这道题目就比较简单了。
输入有两种，分别是两头牛最多距离多远和两头牛最少相隔多远。这个条件可以很容易的转化为不等式来书写。
程序代码
|
|
性能分析
同上题一样，使用$SPFA$算法，复杂度类似。
编程技术技巧
本题就是差分约束系统的基础题型，思想和前面的$3$题类似，没有特别的技巧。